<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.8.0">
    

    

    



    <meta charset="utf-8">
    
    
    
    
    <title>算法初探-冒泡排序及优化 | lafen | lafen&#39;s personal blog</title>
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    
    <meta name="theme-color" content="#3F51B5">
    
    
    <meta name="keywords" content="js,算法">
    <meta name="description" content="常见经典算法初探——冒泡排序现有数组需要排序 1var arr = [1, 2, 3, 4, 5, 6, 7, 8, 10, 9] 1. 冒泡排序12345678910111213function sort(arr) &amp;#123;    var tmp = 0    for(var i = 0; i &amp;lt; arr.length - 1; i++) &amp;#123;        for(var j">
<meta name="keywords" content="js,算法">
<meta property="og:type" content="article">
<meta property="og:title" content="算法初探-冒泡排序及优化">
<meta property="og:url" content="https://lafen.gitee.io/2019/12/11/算法初探-冒泡排序及优化/算法初探-冒泡排序及优化/index.html">
<meta property="og:site_name" content="lafen">
<meta property="og:description" content="常见经典算法初探——冒泡排序现有数组需要排序 1var arr = [1, 2, 3, 4, 5, 6, 7, 8, 10, 9] 1. 冒泡排序12345678910111213function sort(arr) &amp;#123;    var tmp = 0    for(var i = 0; i &amp;lt; arr.length - 1; i++) &amp;#123;        for(var j">
<meta property="og:locale" content="zh-CN">
<meta property="og:updated_time" content="2019-12-11T02:42:30.828Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="算法初探-冒泡排序及优化">
<meta name="twitter:description" content="常见经典算法初探——冒泡排序现有数组需要排序 1var arr = [1, 2, 3, 4, 5, 6, 7, 8, 10, 9] 1. 冒泡排序12345678910111213function sort(arr) &amp;#123;    var tmp = 0    for(var i = 0; i &amp;lt; arr.length - 1; i++) &amp;#123;        for(var j">
    
        <link rel="alternate" type="application/atom+xml" title="lafen" href="/atom.xml">
    
    <link rel="shortcut icon" href="/img/favicon.ico">
    <link rel="stylesheet" href="//unpkg.com/hexo-theme-material-indigo@latest/css/style.css">
    <script>window.lazyScripts=[]</script>

    <!-- custom head -->
    

</head>

<body>
    <div id="loading" class="active"></div>

    <aside id="menu" class="hide">
  <div class="inner flex-row-vertical">
    <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menu-off">
        <i class="icon icon-lg icon-close"></i>
    </a>
    <div class="brand-wrap" style="background-image:url(/img/brand.jpg)">
      <div class="brand">
        <a href="/" class="avatar waves-effect waves-circle waves-light">
          <img src="/img/avatar.jpg">
        </a>
        <hgroup class="introduce">
          <h5 class="nickname">lafen</h5>
          <a href="mailto:1031822863@qq.com" title="1031822863@qq.com" class="mail">1031822863@qq.com</a>
        </hgroup>
      </div>
    </div>
    <div class="scroll-wrap flex-col">
      <ul class="nav">
        
            <li class="waves-block waves-effect">
              <a href="/">
                <i class="icon icon-lg icon-home"></i>
                home
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/archives">
                <i class="icon icon-lg icon-archives"></i>
                Archives
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/tags">
                <i class="icon icon-lg icon-tags"></i>
                Tags
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="/categories">
                <i class="icon icon-lg icon-th-list"></i>
                Categories
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://github.com/zhongxiaotian" target="_blank">
                <i class="icon icon-lg icon-github"></i>
                Github
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="http://www.weibo.com/" target="_blank">
                <i class="icon icon-lg icon-weibo"></i>
                Weibo
              </a>
            </li>
        
            <li class="waves-block waves-effect">
              <a href="https://gitee.com/lafen" target="_blank">
                <i class="icon icon-lg icon-link"></i>
                Gitee
              </a>
            </li>
        
      </ul>
    </div>
  </div>
</aside>

    <main id="main">
        <header class="top-header" id="header">
    <div class="flex-row">
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light on" id="menu-toggle">
          <i class="icon icon-lg icon-navicon"></i>
        </a>
        <div class="flex-col header-title ellipsis">算法初探-冒泡排序及优化</div>
        
        <div class="search-wrap" id="search-wrap">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="back">
                <i class="icon icon-lg icon-chevron-left"></i>
            </a>
            <input type="text" id="key" class="search-input" autocomplete="off" placeholder="输入感兴趣的关键字">
            <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="search">
                <i class="icon icon-lg icon-search"></i>
            </a>
        </div>
        
        
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="menuShare">
            <i class="icon icon-lg icon-share-alt"></i>
        </a>
        
    </div>
</header>
<header class="content-header post-header">

    <div class="container fade-scale">
        <h1 class="title">算法初探-冒泡排序及优化</h1>
        <h5 class="subtitle">
            
                <time datetime="2019-12-11T02:40:40.000Z" itemprop="datePublished" class="page-time">
  2019-12-11
</time>


	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/算法/">算法</a><ul class="article-category-list-child"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/算法/js/">js</a></li></ul></li></ul>

            
        </h5>
    </div>

    


</header>


<div class="container body-wrap">
    
    <aside class="post-widget">
        <nav class="post-toc-wrap post-toc-shrink" id="post-toc">
            <h4>TOC</h4>
            <ol class="post-toc"><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#常见经典算法初探——冒泡排序"><span class="post-toc-number">1.</span> <span class="post-toc-text">常见经典算法初探——冒泡排序</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#1-冒泡排序"><span class="post-toc-number">1.1.</span> <span class="post-toc-text">1. 冒泡排序</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#2-冒泡排序优化一——元素交换标志"><span class="post-toc-number">1.2.</span> <span class="post-toc-text">2. 冒泡排序优化一——元素交换标志</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#3-冒泡排序优化二——无序边界"><span class="post-toc-number">1.3.</span> <span class="post-toc-text">3. 冒泡排序优化二——无序边界</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#4-冒泡排序优化三——鸡尾酒排序"><span class="post-toc-number">1.4.</span> <span class="post-toc-text">4. 冒泡排序优化三——鸡尾酒排序</span></a></li></ol></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#最后"><span class="post-toc-number">2.</span> <span class="post-toc-text">最后</span></a></li></ol>
        </nav>
    </aside>


<article id="post-算法初探-冒泡排序及优化/算法初探-冒泡排序及优化" class="post-article article-type-post fade" itemprop="blogPost">

    <div class="post-card">
        <h1 class="post-card-title">算法初探-冒泡排序及优化</h1>
        <div class="post-meta">
            <time class="post-time" title="2019-12-11 10:40:40" datetime="2019-12-11T02:40:40.000Z" itemprop="datePublished">2019-12-11</time>

            
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/算法/">算法</a><ul class="article-category-list-child"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/算法/js/">js</a></li></ul></li></ul>



            
<span id="busuanzi_container_page_pv" title="文章总阅读量" style="display:none">
    <i class="icon icon-eye icon-pr"></i><span id="busuanzi_value_page_pv"></span>
</span>


        </div>
        <div class="post-content" id="post-content" itemprop="postContent">
            <h3 id="常见经典算法初探——冒泡排序"><a href="#常见经典算法初探——冒泡排序" class="headerlink" title="常见经典算法初探——冒泡排序"></a>常见经典算法初探——冒泡排序</h3><p>现有数组需要排序</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> arr = [<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>, <span class="number">8</span>, <span class="number">10</span>, <span class="number">9</span>]</span><br></pre></td></tr></table></figure>
<h4 id="1-冒泡排序"><a href="#1-冒泡排序" class="headerlink" title="1. 冒泡排序"></a>1. 冒泡排序</h4><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">sort</span>(<span class="params">arr</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">var</span> tmp = <span class="number">0</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">var</span> i = <span class="number">0</span>; i &lt; arr.length - <span class="number">1</span>; i++) &#123;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">var</span> j = <span class="number">0</span>; j &lt; arr.length - i - <span class="number">1</span>; j++) &#123;</span><br><span class="line">            <span class="comment">// 前者大，则交换</span></span><br><span class="line">            <span class="keyword">if</span>(arr[j] &gt; arr[j + <span class="number">1</span>]) &#123;</span><br><span class="line">                tmp = arr[j]</span><br><span class="line">                arr[j] = arr[j + <span class="number">1</span>]</span><br><span class="line">                arr[j + <span class="number">1</span>] = tmp</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong>外层循环控制第几轮比较，内层循环控制两元素循环比较交换</strong></p>
<p><strong>第一轮</strong>比较交换过程如下</p>
<ul>
<li><code>1</code> 和 <code>2</code> 比较，后者大，位置不变，此时 [<strong>1</strong>, <strong>2</strong>, 3, 4, 5, 6, 7, 8, 10, 9]</li>
<li><code>2</code> 和 <code>3</code> 比较，后者大，位置不变，此时 [1, <strong>2</strong>, <strong>3</strong>, 4, 5, 6, 7, 8, 10, 9]</li>
<li>…</li>
<li><code>10</code> 和 <code>9</code> 比较，前者大，交换位置，此时 [1, 2, 3, 4, 5, 6, 7, 8, <strong>9</strong>, <strong>10</strong>]</li>
</ul>
<p>第一轮得出最大的 <code>10</code> ，冒泡到数组最末端，<code>[10]</code> 此为<strong>有序区</strong></p>
<p><strong>第二轮</strong>比较</p>
<ul>
<li><code>1</code> 和 <code>2</code> 比较，后者大，位置不变，此时 [<strong>1</strong>, <strong>2</strong>, 3, 4, 5, 6, 7, 8, 9, 10]</li>
<li>…</li>
<li><code>8</code> 和 <code>9</code> 比较，后者大，位置不变，此时 [1, 2, 3, 4, 5, 6, 7, <strong>8</strong>, <strong>9</strong>, 10]</li>
</ul>
<p>第二轮比较得出第二大为 <code>9</code> ，已经是在倒数第二位中，有序区为 <code>[9, 10]</code></p>
<p>在以上的数组排序过程中，我们发现，在<strong>第一轮</strong>排序的过程中，只需交换 <code>10</code> 和 <code>9</code> 的位置，该数组就已经是<strong>有序</strong>的了，但是冒泡排序依旧兢兢业业的继续进行着每一轮排序，针对这个可以进行以下优化</p>
<h4 id="2-冒泡排序优化一——元素交换标志"><a href="#2-冒泡排序优化一——元素交换标志" class="headerlink" title="2. 冒泡排序优化一——元素交换标志"></a>2. 冒泡排序优化一——元素交换标志</h4><p>假设在一轮比较中，<strong>没有发生元素交换</strong>的时候，我们就认为该数组已经是<strong>有序</strong>的了，为此设置一个标记 <code>isSorted</code> 来进行记录，在进行一轮比较滞后，如果没有元素交换，则直接退出循环即可，以下是代码实现</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">sort</span>(<span class="params">arr</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">var</span> tmp = <span class="number">0</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">var</span> i = <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">        <span class="keyword">var</span> isSorted = <span class="literal">true</span> <span class="comment">// 默认这一轮排序已经是有序的了</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">var</span> j = <span class="number">0</span>; j &lt; arr.length - i - <span class="number">1</span>; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(arr[j] &gt; arr[j + <span class="number">1</span>]) &#123;</span><br><span class="line">                tmp = arr[j]</span><br><span class="line">                arr[j] = arr[j + <span class="number">1</span>]</span><br><span class="line">                arr[j + <span class="number">1</span>] = tmp</span><br><span class="line">                isSorted = <span class="literal">false</span> <span class="comment">// 发生了元素交换，则不是有序的</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 未发生元素交换时，结束外层循环</span></span><br><span class="line">        <span class="keyword">if</span>(isSorted) &#123;</span><br><span class="line">            <span class="keyword">break</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="3-冒泡排序优化二——无序边界"><a href="#3-冒泡排序优化二——无序边界" class="headerlink" title="3. 冒泡排序优化二——无序边界"></a>3. 冒泡排序优化二——无序边界</h4><p>如有以下数组需要排序，可以看到后面的 <code>[6, 7, 8, 9]</code> 都已经是有序的了，在此之前的元素均为无序，则我们称前面的 <code>1</code> 元素所在的索引为<strong>无序边界</strong></p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> arr = [<span class="number">4</span>, <span class="number">5</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">1</span>, <span class="number">6</span>, <span class="number">7</span>, <span class="number">8</span>, <span class="number">9</span>]</span><br></pre></td></tr></table></figure>
<p>我们知道冒泡排序的过程如下</p>
<ul>
<li><code>4</code> 和 <code>5</code> 比较，后者大，位置不变</li>
<li><code>5</code> 和 <code>2</code> 比较，前者大，交换位置，此时 arr = [4, <strong>2</strong>, <strong>5</strong>, 3, 1, 6, 7, 8, 9]</li>
<li><code>5</code> 和 <code>3</code> 比较，前者大，交换位置，此时 arr = [4, 2, <strong>3</strong>, <strong>5</strong>, 1, 6, 7, 8, 9]</li>
<li><code>5</code> 和 <code>1</code> 比较，前者大，交换位置，此时 arr = [4, 2, 3, <strong>1</strong>, <strong>5</strong>, 6, 7, 8, 9]</li>
<li><code>5</code> 和 <code>6</code> 比较，后者大，位置不变，此时 arr = [4, 2, 3, 1, <strong>5</strong>, <strong>6</strong>, 7, 8, 9]</li>
<li>…</li>
<li>如果按照常规的冒泡排序，则会一直比较到最后 <code>8</code> 和 <code>9</code>，然后又回到前面 <code>4</code> 和 <code>2</code> 的比较，开始<strong>第二轮</strong>循环比较，直到倒数第二个元素</li>
</ul>
<p>但是第一轮中的比较 <code>[5, 6, 7, 8, 9]</code> 其实已经是<strong>有序</strong>的了，但是冒泡排序依旧一个个去比较，这就是可以针对这个点进行优化的地方，即记录<strong>无序边界</strong>，下一轮比较只需比较到<strong>无序边界</strong>即可</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">sort</span>(<span class="params">arr</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">var</span> tmp = <span class="number">0</span></span><br><span class="line">    <span class="keyword">var</span> lastExchangeIndex = <span class="number">0</span> <span class="comment">// 最后进行交换的元素位置</span></span><br><span class="line">    <span class="keyword">var</span> sortBorder = arr.length - <span class="number">1</span> <span class="comment">// 无序边界，每一轮只比较到边界</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">var</span> i = <span class="number">0</span>; i &lt; arr.length - <span class="number">1</span>; i++) &#123;</span><br><span class="line">        <span class="keyword">var</span> isSorted = <span class="literal">true</span> <span class="comment">// 有序标记，默认这一轮比较为有序</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">var</span> j = <span class="number">0</span>; j &lt; sortBorder; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(arr[j] &gt; arr[j + <span class="number">1</span>]) &#123;</span><br><span class="line">                tmp = arr[j]</span><br><span class="line">                arr[j] = arr[j + <span class="number">1</span>]</span><br><span class="line">                arr[j + <span class="number">1</span>] = tmp</span><br><span class="line">                isSorted = <span class="literal">false</span> <span class="comment">// 发生了元素交换，则不是有序</span></span><br><span class="line">                lastExchangeIndex = j <span class="comment">// 记录当前的最后一次交换的元素边界</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        sortBoder = lastExchangeIndex <span class="comment">// 最后一次交换元素的索引即为无序边界</span></span><br><span class="line">        <span class="keyword">if</span>(isSorted) &#123;</span><br><span class="line">            <span class="keyword">break</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="4-冒泡排序优化三——鸡尾酒排序"><a href="#4-冒泡排序优化三——鸡尾酒排序" class="headerlink" title="4. 冒泡排序优化三——鸡尾酒排序"></a>4. 冒泡排序优化三——鸡尾酒排序</h4><p>鸡尾酒排序算法是<strong>双向</strong>的冒泡排序，第一轮<strong>从左到右</strong>按照从小到大排序，然后<strong>从右到左</strong>按照从大到小排序，第二轮再重复，如此往复排序，即为<strong>鸡尾酒排序</strong></p>
<p>现有以下数组</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> arr = [<span class="number">9</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>, <span class="number">8</span>, <span class="number">1</span>]</span><br></pre></td></tr></table></figure>
<p>普通冒泡排序过程</p>
<ul>
<li>第一轮，会找到 <code>9</code> 是最大的，会把 <code>9</code> 冒泡到最后一位，即 [2, 3, 4, 5, 6, 7, 8, 1, <strong>9</strong>]</li>
<li>第二轮，会找到 <code>8</code> 是剩余的最大的，冒泡到最后得 [2, 3, 4, 5, 6, 7, <strong>1</strong>, <strong>8</strong>, 9]</li>
<li>…</li>
</ul>
<p>这样一直往下循环，直到 <code>1</code> 被循环到第一位</p>
<p>但是问题也很明显，第一轮循环过后，<code>1</code> 前面的明明已经是<strong>有序</strong>的了，这时候只需要对 <code>1</code> 进行排序就可以了，但是程序并不知道是 <code>1</code> 需要排序啊，这时候，<strong>鸡尾酒排序</strong>就派上用场了</p>
<p><strong>在第一轮排序中</strong>，鸡尾酒排序会<strong>先从左往右</strong>排序，即将 <code>9</code> 移动到最后一位，然后再从<strong>右往左</strong>，按照从<strong>大到小</strong>，再进行一次排序，即一轮循环里面会出现<strong>正向排序</strong>（如上第一轮过程）和<strong>反向排序</strong>，接下来看看<strong>反向排序</strong>里面会发生什么？</p>
<ul>
<li>从 <code>[2, 3, 4, 5, 6, 7, 8, 1, 9]</code> 进行<strong>反向排序</strong>，会发现 <code>1</code> 比 <code>8</code> 小，则将 <code>1</code> 向<strong>左</strong>冒泡，<code>1</code> 又比 <code>7</code> 小，继续向<strong>左</strong>冒泡，直到冒泡到数组的第一位</li>
</ul>
<p>这样下来发现，数组已经排好序，下一轮排序的时候，没有发生元素交换，则说明已经为有序了，直接结束循环，这样，总共也就<strong>两轮</strong>排序，就搞定了，接下来实现一下代码</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">sort</span>(<span class="params">arr</span>) </span>&#123;</span><br><span class="line">    <span class="keyword">var</span> tmp = <span class="number">0</span></span><br><span class="line">    <span class="comment">// 因为是双向比较，所以比较次数为原来的一半即可</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">var</span> i = <span class="number">0</span>; i &lt; arr.length/<span class="number">2</span>; i++) &#123;</span><br><span class="line">        <span class="keyword">var</span> isSorted = <span class="literal">true</span> <span class="comment">// 默认有序</span></span><br><span class="line">        <span class="comment">// 从左往右，升序</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">var</span> j = i; j &lt; arr.length - i - <span class="number">1</span>; j++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(arr[j] &gt; arr[j + <span class="number">1</span>]) &#123;</span><br><span class="line">                tmp = arr[j]</span><br><span class="line">                arr[j] = arr[j + <span class="number">1</span>]</span><br><span class="line">                arr[j + <span class="number">1</span>] = tmp</span><br><span class="line">                isSorted = <span class="literal">false</span> <span class="comment">// 发生了元素交换，置为false</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(isSorted) &#123;</span><br><span class="line">           <span class="keyword">break</span></span><br><span class="line">        &#125;</span><br><span class="line">        isSorted = <span class="literal">true</span> <span class="comment">// 先重置有序标志</span></span><br><span class="line">        <span class="comment">// 从右往左，降序</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">var</span> j = arr.length - i - <span class="number">1</span>; j &gt; i; j--) &#123;</span><br><span class="line">            <span class="keyword">if</span>(arr[j] &lt; arr[j - <span class="number">1</span>]) &#123;</span><br><span class="line">                tmp = arr[j]</span><br><span class="line">                arr[j] = arr[j - <span class="number">1</span>]</span><br><span class="line">                arr[j - <span class="number">1</span>] = tmp</span><br><span class="line">                isSorted = <span class="literal">false</span> <span class="comment">// 发生了元素交换，置为false</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(isSorted) &#123;</span><br><span class="line">            <span class="keyword">break</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>可以看出</p>
<ul>
<li>鸡尾酒排序代码多了一倍</li>
<li>鸡尾酒排序适用于部分已有序的数组（如上述例子中的数组），但是对于完全逆序的数组，鸡尾酒排序与冒泡排序的效率都很差</li>
<li>还可以加上边界判断</li>
</ul>
<h3 id="最后"><a href="#最后" class="headerlink" title="最后"></a>最后</h3><p>最近水得有点严重了，睡眠成了个大问题…</p>

        </div>

        <blockquote class="post-copyright">
    
    <div class="content">
        
<span class="post-time">
    最后更新时间：<time datetime="2019-12-11T02:42:30.828Z" itemprop="dateUpdated">2019-12-11 10:42:30</time>
</span><br>


        
        关于学习类文章网上已经有非常多，而此处文章都是我在学习过程中整理摘录的笔记，参考文章可以点击文末的参考链接进行查阅
        
    </div>
    
    <footer>
        <a href="https://lafen.gitee.io">
            <img src="/img/avatar.jpg" alt="lafen">
            lafen
        </a>
    </footer>
</blockquote>

        
<div class="page-reward">
    <a id="rewardBtn" href="javascript:;" class="page-reward-btn waves-effect waves-circle waves-light">赏</a>
</div>



        <div class="post-footer">
            
	<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/js/">js</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/算法/">算法</a></li></ul>


            
<div class="page-share-wrap">
    

<div class="page-share" id="pageShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=https://lafen.gitee.io/2019/12/11/算法初探-冒泡排序及优化/算法初探-冒泡排序及优化/&title=《算法初探-冒泡排序及优化》 — lafen&pic=https://lafen.gitee.io/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=https://lafen.gitee.io/2019/12/11/算法初探-冒泡排序及优化/算法初探-冒泡排序及优化/&title=《算法初探-冒泡排序及优化》 — lafen&source=lafen's personal blog" data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=https://lafen.gitee.io/2019/12/11/算法初探-冒泡排序及优化/算法初探-冒泡排序及优化/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《算法初探-冒泡排序及优化》 — lafen&url=https://lafen.gitee.io/2019/12/11/算法初探-冒泡排序及优化/算法初探-冒泡排序及优化/&via=https://lafen.gitee.io" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=https://lafen.gitee.io/2019/12/11/算法初探-冒泡排序及优化/算法初探-冒泡排序及优化/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>



    <a href="javascript:;" id="shareFab" class="page-share-fab waves-effect waves-circle">
        <i class="icon icon-share-alt icon-lg"></i>
    </a>
</div>



        </div>
    </div>

    
<nav class="post-nav flex-row flex-justify-between">
  
    <div class="waves-block waves-effect prev">
      <a href="/2019/12/14/2019年终总结/2019年终总结/" id="post-prev" class="post-nav-link">
        <div class="tips"><i class="icon icon-angle-left icon-lg icon-pr"></i> Prev</div>
        <h4 class="title">2019年终总结</h4>
      </a>
    </div>
  

  
    <div class="waves-block waves-effect next">
      <a href="/2019/12/03/vue-源码笔记-初始化方法-2/vue-源码笔记-初始化方法-2/" id="post-next" class="post-nav-link">
        <div class="tips">Next <i class="icon icon-angle-right icon-lg icon-pl"></i></div>
        <h4 class="title">vue-源码笔记-初始化方法(2)</h4>
      </a>
    </div>
  
</nav>



    




















</article>

<div id="reward" class="page-modal reward-lay">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <h3 class="reward-title">
        <i class="icon icon-quote-left"></i>
        打笔巨款？~
        <i class="icon icon-quote-right"></i>
    </h3>
    <div class="reward-content">
        
        <div class="reward-code">
            <img id="rewardCode" src="/img/wechat.jpg" alt="打赏二维码">
        </div>
        
        <label class="reward-toggle">
            <input id="rewardToggle" type="checkbox" class="reward-toggle-check" data-wechat="/img/wechat.jpg" data-alipay="/img/alipay.jpg">
            <div class="reward-toggle-ctrol">
                <span class="reward-toggle-item wechat">微信</span>
                <span class="reward-toggle-label"></span>
                <span class="reward-toggle-item alipay">支付宝</span>
            </div>
        </label>
        
    </div>
</div>



</div>

        <footer class="footer">
    <div class="top">
        
<p>
    <span id="busuanzi_container_site_uv" style="display:none">
        站点总访客数：<span id="busuanzi_value_site_uv"></span>
    </span>
    <span id="busuanzi_container_site_pv" style="display:none">
        站点总访问量：<span id="busuanzi_value_site_pv"></span>
    </span>
</p>


        <p>
            
                <span><a href="/atom.xml" target="_blank" class="rss" title="rss"><i class="icon icon-lg icon-rss"></i></a></span>
            
            <span>博客内容遵循 <a rel="license" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">知识共享 署名 - 非商业性 - 相同方式共享 4.0 国际协议</a></span>
        </p>
    </div>
    <div class="bottom">
        <p><span>lafen &copy; 2019 - 2020</span>
            <span>
                
                Power by <a href="http://hexo.io/" target="_blank">Hexo</a> Theme <a href="https://github.com/yscoder/hexo-theme-indigo" target="_blank">indigo</a>
            </span>
        </p>
    </div>
</footer>

    </main>
    <div class="mask" id="mask"></div>
<a href="javascript:;" id="gotop" class="waves-effect waves-circle waves-light"><span class="icon icon-lg icon-chevron-up"></span></a>



<div class="global-share" id="globalShare">
    <ul class="reset share-icons">
      <li>
        <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=https://lafen.gitee.io/2019/12/11/算法初探-冒泡排序及优化/算法初探-冒泡排序及优化/&title=《算法初探-冒泡排序及优化》 — lafen&pic=https://lafen.gitee.io/img/avatar.jpg" data-title="微博">
          <i class="icon icon-weibo"></i>
        </a>
      </li>
      <li>
        <a class="weixin share-sns wxFab" href="javascript:;" data-title="微信">
          <i class="icon icon-weixin"></i>
        </a>
      </li>
      <li>
        <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=https://lafen.gitee.io/2019/12/11/算法初探-冒泡排序及优化/算法初探-冒泡排序及优化/&title=《算法初探-冒泡排序及优化》 — lafen&source=lafen's personal blog" data-title=" QQ">
          <i class="icon icon-qq"></i>
        </a>
      </li>
      <li>
        <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=https://lafen.gitee.io/2019/12/11/算法初探-冒泡排序及优化/算法初探-冒泡排序及优化/" data-title=" Facebook">
          <i class="icon icon-facebook"></i>
        </a>
      </li>
      <li>
        <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《算法初探-冒泡排序及优化》 — lafen&url=https://lafen.gitee.io/2019/12/11/算法初探-冒泡排序及优化/算法初探-冒泡排序及优化/&via=https://lafen.gitee.io" data-title=" Twitter">
          <i class="icon icon-twitter"></i>
        </a>
      </li>
      <li>
        <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=https://lafen.gitee.io/2019/12/11/算法初探-冒泡排序及优化/算法初探-冒泡排序及优化/" data-title=" Google+">
          <i class="icon icon-google-plus"></i>
        </a>
      </li>
    </ul>
 </div>


<div class="page-modal wx-share" id="wxShare">
    <a class="close" href="javascript:;"><i class="icon icon-close"></i></a>
    <p>扫一扫，分享到微信</p>
    <img src="" alt="微信分享二维码">
</div>




    <script src="//cdn.bootcss.com/node-waves/0.7.4/waves.min.js"></script>
<script>
var BLOG = { ROOT: '/', SHARE: true, REWARD: true };


</script>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/main.min.js"></script>


<div class="search-panel" id="search-panel">
    <ul class="search-result" id="search-result"></ul>
</div>
<template id="search-tpl">
<li class="item">
    <a href="{path}" class="waves-block waves-effect">
        <div class="title ellipsis" title="{title}">{title}</div>
        <div class="flex-row flex-middle">
            <div class="tags ellipsis">
                {tags}
            </div>
            <time class="flex-col time">{date}</time>
        </div>
    </a>
</li>
</template>

<script src="//unpkg.com/hexo-theme-material-indigo@latest/js/search.min.js" async></script>






<script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>



<script>
(function() {
    var OriginTitile = document.title, titleTime;
    document.addEventListener('visibilitychange', function() {
        if (document.hidden) {
            document.title = '死鬼去哪里了！';
            clearTimeout(titleTime);
        } else {
            document.title = '(つェ⊂)咦!又好了!';
            titleTime = setTimeout(function() {
                document.title = OriginTitile;
            },2000);
        }
    });
})();
</script>



<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"scale":1,"jsonPath":"/live2dw/assets/shizuku.model.json"},"display":{"positon":"right","width":150,"height":300},"mobile":{"show":true,"scale":0.8},"react":{"opacity":0.8,"opacityDefault":0.8,"opacityOnHover":0.6},"log":false});</script></body>
</html>
